class IndexWrong extends RuntimeException{
    public IndexWrong() {
    }

    public IndexWrong(String message) {
        super(message);
    }
}

public class MyLinkedList {
    static class ListNode {
        public int val;//数值域
        public ListNode prev;//前面的地址
        public ListNode next;//后面的地址

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;//双向链表的头结点
    public ListNode tail;//双向链表的尾结点

    /*
    * NO.1
    * @ 打印双向链表每个节点的值
    * */
    public void disPlay() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    /*
    * NO.2
    * @ 求双向链表元素个数
    * */
    public int size() {
        ListNode cur = this.head;
        int count = 0;//计数器
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    /*
    * No.3
    * @ 在双向链表中查找是否有key
    * */
    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /*
    * NO.4
    * @ 头插法
    * */
    public void addFirst(int data) {
        ListNode node = new ListNode(data);//新节点
        //双向链表为空的情况
        if (this.head == null) {
            //头和尾直接赋给node结点
            this.head = node;
            this.tail = node;
        }else { //有很多结点的情况
            node.next = this.head;//node的next域指向head
            this.head.prev = node;//原head的prev域指向node的地址
            head = node;//将node结点改成新头结点
        }
    }

    /*
    * NO.5
    * @ 尾插法
    * */
    public void addLast(int data) {
        ListNode node = new ListNode(data);//新节点
        //双向链表为空的情况
        if (this.head == null) {
            this.head = node;
            this.tail = node;
        }else { //多个结点的情况
            this.tail.next = node;//尾结点地址域指向node结点
            node.prev =this.tail;//node指向它的前驱
            this.tail = node;//尾结点改成node
        }
    }

    /*
    * NO.6
    * @ 在任意位置插入第一个数据结点为0的下标
    * */
    //下表为逻辑上定义的下标
    public void addIndex(int index, int data) throws IndexWrong{
        //index位置要合法
        if (index < 0 || index > size()) {
            System.out.println("index位置不合法！！！");
            throw new RuntimeException("index位置不合法！！！");
        }

        //头插
        if (index == 0) {
            addFirst(data);
            return;
        }

        //尾插
        if (index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = findIndexListNode(index);//此时cur即是index的位置

        //在中间插，不是头不是尾就是中间
        ListNode node = new ListNode(data);
        node.next = cur;//node的地址指向cur
        cur.prev.next = node;//index位置的前驱的地址指向node
        node.prev = cur.prev;//node前驱的地址指向cur的前驱
        cur.prev = node;//cur前驱的地址指向node
    }

    //求cur的位置
    private ListNode findIndexListNode(int index) {
        ListNode cur = this.head;
        while (index != 0) {
            cur = cur.next;//指向下一个
            index--;
        }
        return cur;
    }

    /*
    * NO.7
    * @ 删除第一次出现的key结点
    * */
    public void remove(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                //如果key在头结点
                if (cur == this.head) {
                    this.head = this.head.next;//头结点指向它的下一个
                    if (this.head != null) {
                        this.head.prev = null;//改掉head指向前驱的地址
                    }else {
                        this.tail = null;//将tail指向空
                    }

                }else{ //如果key不是头结点
                    cur.prev.next = cur.next;//cur的前驱指向cur的后面
                    //cur不等于空说明cur此时不指向尾结点
                    if(cur.next != null) {
                       cur.next.prev = cur.prev;//cur后面的结点的前驱指向cur的前驱
                    }else { //指向尾结点
                        this.tail = cur.prev;//将tail前移一个结点的位置
                    }
                }
                return;
            }
            cur = cur.next;//指向下一个
        }
    }

    /*
    * NO.8
    * @ 删除所有值为key的结点
    * */
    public void removeAllKey(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                //如果key在头结点
                if (cur == this.head) {
                    this.head = this.head.next;//头结点指向它的下一个
                    if (this.head != null) {
                        this.head.prev = null;//改掉head指向前驱的地址
                    }else {
                        this.tail = null;//将tail指向空
                    }

                }else{ //如果key不是头结点
                    cur.prev.next = cur.next;//cur的前驱指向cur的后面
                    //cur不等于空说明cur此时不指向尾结点
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;//cur后面的结点的前驱指向cur的前驱
                    }else { //指向尾结点
                        this.tail = cur.prev;//将tail前移一个结点的位置
                    }
                }
            }
            cur = cur.next;//指向下一个
        }
    }

    /*
    * NO.9
    * @ 清空双向链表
    * */
    public void clear() {
        ListNode cur = this.head;
        //清空中间的结点
        while (cur != null) {
            ListNode curNext = cur.next; //始终指向cur的下一个
            //置为空
            cur.prev = null;
            cur.next = null;
            cur = cur.next;//指向下一个
        }

        //两端的结点
        this.head = null;
        this.tail = null;
    }

    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        //测试头插和尾插
        myLinkedList.addFirst(1);
        myLinkedList.addFirst(2);
        myLinkedList.addFirst(3);
        myLinkedList.addFirst(4);
        myLinkedList.addFirst(5);
        myLinkedList.addLast(1);
        myLinkedList.addLast(2);
        myLinkedList.addLast(3);
        myLinkedList.addLast(4);
        myLinkedList.addLast(5);
        myLinkedList.disPlay();//测试打印双向链表的方法
        //测试求双向链表个数的方法
        System.out.println("个数：" + myLinkedList.size());
        //测试双向链表中是否含有key
        System.out.println(myLinkedList.contains(12));//false
        System.out.println(myLinkedList.contains(4));//true
        //测试在任意位置插
        myLinkedList.addIndex(5, 6);
        myLinkedList.disPlay();
        //测试删除第一次出现的key
        myLinkedList.remove(5);
        myLinkedList.disPlay();
        //测试删除所有值为key的结点
        myLinkedList.removeAllKey(5);
        myLinkedList.disPlay();
    }
}
